package com.rising.face.ali.bishi.myQueue;

import java.util.Stack;

/**
 * @Author: rising
 * @Description:
 * 队列应支持push(element)，pop() 和 top()，其中pop是弹出队列中的第一个(最前面的)元素。
 * pop和top方法都应该返回第一个元素的值。
 * 样例：比如push(1), pop(), push(2), push(3), top(), pop()，你应该返回1，2和2
 * 要求：仅使用两个栈来实现它，不使用任何其他数据结构，push，pop 和 top的复杂度都应该是均摊O(1)的
 * @Date: create in 2021/2/28 19:30
 */
public class MyQueue {
    Stack<Integer> p = new Stack<>();
    Stack<Integer> q = new Stack<>();

    //push方法
    public void push(int x) {
        while(!p.empty()){
            q.push(p.lastElement());
            p.pop();
        }
        p.push(x);
        while(!q.empty()){
            p.push(q.lastElement());
            q.pop();
        }
    }

    //移除队头元素
    public int pop() {
        if (empty()) {
            throw new RuntimeException("队列为空");
        }
        int res=p.lastElement();
        p.pop();
        return res;
    }

    //获取队头元素
    public int top() {
        if (empty()) {
            throw new RuntimeException("队列为空");
        }
        return p.lastElement();
    }

    public boolean empty() {
        return p.empty();
    }

    public static void main(String[] args) {
        //比如push(1), pop(), push(2), push(3), top(), pop()，你应该返回1，2和2
        MyQueue myQueue = new MyQueue();
        myQueue.push(1);
        System.out.println("pop()->" + myQueue.pop());
        myQueue.push(2);
        myQueue.push(3);
        myQueue.push(4);
        myQueue.push(5);
        System.out.println("top()->" + myQueue.top());
        System.out.println("pop()->" + myQueue.pop());
        System.out.println("pop()->" + myQueue.pop());
        System.out.println("pop()->" + myQueue.pop());
        System.out.println("top()->" + myQueue.top());

        Stack<Integer> stack = new Stack<>();
        stack.push(1);
        stack.push(2);
        stack.push(3);
        System.out.println("lastElement = " + stack.lastElement());
        System.out.println("pop = " + stack.pop());
    }
}
